#include <iostream>
#include "BinarySearchTree.h"
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
void BST_sort(std::vector<T> &_data)
{
    BinarySearchTree<T> tr;
    for(int i=0;i<_data.size();i++)
    tr.insert(_data[i]);
    //此时二叉树已排序完毕，只需将其覆盖_data
    _data.clear();
    while(!tr.isEmpty())
    {
        T x=tr.findMin();
        tr.remove(x);
        _data.push_back(x);
    }

}
template <typename T>
void Randomized_BST_sort(std::vector<T> &_data)
{
    random_shuffle(_data.begin(),_data.end());
    BST_sort(_data);
}
int main()
{
    srand(unsigned)time(NULL);
    vector<int> a;
    for(int i=0;i<10;i++)
    {
        a.push_back(rand()&99);
    }
    //利用ctime生成10个小于100的随机数

    cout<<"here are ten random numbers"<<endl;
    for(int i=0;i<a.size();i++)
        cout<<a[i]<<"\t";
    cout<<endl;
    //输出这些随机数

    Randomized_BST_sort(a);
    //排序

    cout<<"ording..."<<endl;
    for(int i=0;i<a.size();i++)
        cout<<a[i]<<"\t";
    cout<<endl;
    //输出排序

    return 0;

}










